package sgg.algorithm.datastructure.sort;

import java.util.Arrays;

/**
 * @author: Michael
 * @date: 2025/4/30
 * @desc: 基数排序
 */
public class RadixSort {

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("排序前: " + Arrays.toString(arr));
        radixSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }

    public static void radixSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        // 1. 计算最大数字的位数
        int max = Arrays.stream(arr).max().getAsInt();
        int maxDigit = String.valueOf(max).length();

        // 2. 从个位到最高位依次排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    // 按当前位（exp）进行计数排序
    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];      // 存储排序结果
        int[] count = new int[10];      // 0~9 的计数桶

        // 统计当前位各数字的出现次数
        for (int num : arr) {
            int digit = (num / exp) % 10;
            count[digit]++;
        }

        // 计算累计位置（确定元素在output中的最终位置）
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 从后向前遍历，保证稳定性
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // 将排序结果拷贝回原数组
        System.arraycopy(output, 0, arr, 0, n);
    }
}
